2018 CCPC Online

补题进度：4/10

---

题目链接

---

A

题意

题解

---

B

题意

题解

---

C

题意

题解

---

D

• 费马大定理说明了$a^n+b^n=c^n$在$n>2$的时候无解
• 毕达哥拉斯三角形$a^2+b^2=c^2$说明了在给出非斜边的情况下，剩下两边$O(1)$求解方法

直角三角形$a^2+b^2=c^2$整数解的定$a$公式直求法

• $a=2n+1$(奇数)时， $b=2n^2+2n，c=b+1$
• $a=2n$(偶数)时，$b=n^2-1，c=n^2+1$

---

E

题意

题解

---

F

题意

题解

---

G

题意

题解

---

H

题意

题解

---

I

分析

• $n$ 个点全排列实际上和 $n-1$ 条边全排列实质上是一样的
• $n$ 个点两两之间的距离和为 $sum$，答案$ans=sum×(n-1)!$
• n个点两两之间的距离和？
• 考虑每条边的贡献为边两端挂的点$n$和$m$，$2·C(n,1)·C(m,1)·w[i]$。

---

J

分析

• 观察x,y<=1e9，但n只有对1e5，故对n个点离散化
• 考虑每个点$(x,y)$可以转移过来的点$(i,j)(i<x, j<y)$
• 转化成二维的最值问题，可直接排序一维，线段树维护另一维即可

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
int q, n, k, T;

int a[maxn], b[maxn], x[maxn], y[maxn], val[maxn];
int ans;


struct pp
{
    int x, y,val;
    friend bool operator < (pp xx, pp yy)
    {
        if(xx.x!=yy.x)
            return xx.x<yy.x;
        else
            return xx.y>yy.y;
    }
}p[maxn];

struct node
{
    int l,  r, maxx;
}t[maxn<<2];


void build(int x,int l,int r)
{
    t[x].l=l, t[x].r=r;
    if(l==r)
    {
        t[x].maxx=0;
        return;
    }

    int mid=(l+r)/2;
    build(x<<1, l, mid);
    build(x<<1|1, mid+1, r);
    t[x].maxx=max(t[x<<1].maxx, t[x<<1|1].maxx);
    return;
}

void update(int x,int pos, int val)
{
    int l=t[x].l, r=t[x].r;
    if(l==r)
    {
        t[x].maxx=max(t[x].maxx, val);
        return;
    }
    int mid=(l+r)/2;
    int ans=0;
    if(pos<=mid)
    {
        update(x<<1, pos ,val);
    }
    else
        update(x<<1|1, pos, val);
    t[x].maxx=max(t[x<<1].maxx, t[x<<1|1].maxx);
}

int query(int x,int ql, int qr)
{
    int l=t[x].l, r=t[x].r;
    if(ql<=l && qr>=r)
    {
        return t[x].maxx;
    }
    int mid=(l+r)/2;
    int ans=0;
    if(ql<=mid) ans=max(ans, query(x<<1, ql, qr));
    if(qr>mid) ans=max(ans, query(x<<1|1, ql, qr));
    return ans;
}


int main()
{
    scanf("%d", &T);
    while(T--)
    {
        ans=0;
        scanf("%d", &n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d%d%d", &p[i].x, &p[i].y, &p[i].val);
            a[i]=p[i].x;  b[i]=p[i].y;
        }
        sort(a+1, a+n+1);
        sort(b+1, b+n+1);
        for(int i=1;i<=n;i++)
        {
            p[i].x=lower_bound(a+1, a+n+1, p[i].x)-a;
            p[i].y=lower_bound(b+1, b+n+1, p[i].y)-b;
        }
        sort(p+1, p+n+1);
        build(1, 1, n);
        for(int i=1;i<=n;i++)
        {
            int maxx=0;
            if(p[i].y!=1)
            maxx=query(1, 1, p[i].y-1);
            ans=max(p[i].val+maxx, ans);
            update(1, p[i].y, p[i].val+maxx);
        }
        printf("%d\n", ans);
    }
}

---